import org.scalatest.{FunSpec, Matchers}
import org.scalatest.prop.TableDrivenPropertyChecks

class Q35 extends FunSpec with TableDrivenPropertyChecks with Matchers {
  def searchInsert(nums: Array[Int], target: Int): Int = {
    println(s"${nums.mkString("[", ", ", "]")} :$target")
    search(nums, 0, nums.length, target)
  }

  def search(a: Array[Int], s: Int, t: Int, target: Int): Int = {
    println(s"search [$s, $t)")
    if (s < 0) 0
    else if (t > a.length) a.length
    else if (s == t - 1) {
      if (a(s) == target) s
      else if (a(s) < target) s + 1
      else s
    } else if (s == t) s
    else {
      val m = (s + t) / 2
      println(s"a[$m] = ${a(m)}")
      if (a(m) == target) m
      else if (a(m) > target) search(a, s, m, target)
      else search(a, m + 1, t, target)
    }
  }

  val cases = Table(
    ("case", "expected"),
    ((Array(1, 3, 5, 6), 5), 2),
    ((Array(1, 3, 5, 6), 2), 1),
    ((Array(1, 3, 5, 6), 7), 4),
    ((Array(1, 3, 5, 6), 0), 0),
    ((Array(1, 3), 4), 2),
    ((Array(1, 3, 5), 4), 2)
  )

  describe("Search Insert Position") {
    it("cases") {
      forAll(cases) { case ((a: Array[Int], t: Int), e: Int) =>
        searchInsert(a, t) shouldBe e
      }
    }
  }
}
